package com.mdnote.structure.sort;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/27
 * @description 归并排序
 */
public class MergeSort {

    public static void sort(int[] source, int left, int right, int[] temp) {
        int mid = (left + right) / 2;
        if (left < right) {
            // 向左递归
            sort(source, left,  mid, temp);
            // 向右递归
            sort(source, mid + 1, right, temp);

            // 合并
            merge(source, left, mid, right, temp);
        }

    }

    /**
     * 合并两个数组
     * @param source 原数组
     * @param left  左边的元素
     * @param mid 中间的元素
     * @param right 最右边的元素
     * @param temp 临时数组
     */
    private static void merge(int[] source, int left, int mid, int right, int[] temp) {
        int tempArrayIndex = 0;
        // 两个数组的索引
        int leftIndex = left;
        int rightIndex = mid + 1;

        // 合并两个数组
        while (leftIndex <= mid && rightIndex <= right) {
            if (source[leftIndex] < source[rightIndex]) {
                temp[tempArrayIndex] = source[leftIndex];
                leftIndex++;
            } else {
                temp[tempArrayIndex] = source[rightIndex];
                rightIndex++;
            }
            tempArrayIndex++;
        }

        // 吧剩下的内容放入tmp数组中
        while (leftIndex <= mid) {
            temp[tempArrayIndex] = source[leftIndex];
            tempArrayIndex++;
            leftIndex++;
        }
        while (rightIndex <= right) {
            temp[tempArrayIndex] = source[rightIndex];
            tempArrayIndex++;
            rightIndex++;
        }

        // 最后把临时数组拷贝到原数组中,只需要覆盖自己那部分就行
        tempArrayIndex = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            source[tempLeft] = temp[tempArrayIndex];
            tempArrayIndex++;
            tempLeft++;
        }
    }

    public static void main(String[] args) {
        int[] data = {11, 55, 1, 22};
        int[] temp = new int[data.length];
        sort(data, 0, data.length - 1, temp);
        System.out.println(Arrays.toString(data));
    }
}
